Tapestry (P2P)

Tapestry es una infraestructura de red peer-to-peer de superposición que proporciona una tabla de hash distribuida (DHT), encaminamiento e infraestructura de multidifusión para aplicaciones distribuidas.​ Tapestry ofrece eficiencia, escalabilidad, auto-reparación ante fallos y enrutamiento eficiente a los recursos cercanos.

Introducción

Los desarrolladores a través de internet están constantemente proponiendo nuevas aplicaciones distribuidas. Estas nuevas aplicaciones necesitan de una variedad de requisitos en cuanto a la disponibilidad, durabilidad y rendimiento. Una técnica para asegurar que se cumplen estos requisitos ante fallos y cambios es migrar y replicar datos y servicios. Sin embargo, la capacidad para realizar esta técnica se ve muy limitada por la infraestructura de la red en la que se encuentra. La forma tradicional para sacar adelante estas nuevas aplicaciones es adaptarlas a las infraestructuras existentes, a menudo limitando su funcionalidad en gran medida, o estandarizando nuevos protocolos de Internet, lo cual es muy laborioso.

La primera generación de aplicaciones peer-to-peer, incluyendo Napster, Gnutella, MojoNation y Freenet, tenía limitaciones tales como un directorio central (Napster), lo cual limitaba la escalabilidad. Ni Gnutella ni Freenet garantizaban que los archivos pudiesen ser localizados, incluso cuando contaban con una red funcional. Para hacer frente a estos problemas se desarrolló una segunda generación de aplicaciones P2P, estas fueron Tapestry, Chord, Pastry y CAN. Estos modelos implementan un mecanismo básico de enrutamiento basado en claves. Esto permite el encaminamiento determinista de mensajes y adaptación a fallos en nodos en la red. Estas aplicaciones también soportaban interfaces de nivel superior, como tablas de hash distribuidas (DHT) o una capa DOLR. De estas aplicaciones, Pastry es muy similar a Tapestry ya que ambas contienen el mismo algoritmo de enrutamiento, Plaxton.

Tapestry es una infraestructura ampliable que ofrece localización de objetos descentralizada y encaminamiento(DOLR, del inglés: Decentralized Object Location and Routing) enfocado a la eficiencia y a minimizar la latencia, mientras encamina mensajes a los destinos finales ya sean nodos o réplicas de objetos. Esto se logra ya que Tapestry construye localmente tablas de encaminamiento óptimas y los mantiene con el fin de reducir el aumento de la longitud del encaminamiento. Además, Tapestry permite determinar la distribución de acuerdo con las necesidades de una aplicación dada. Del mismo modo, Tapestry permite que las aplicaciones implementen multidifusión en la red superpuesta.

DORL virtualiza los recursos, los destinos finales se identifican mediante identificadores opacos, sin codificar nada sobre su localización física. Esta virtualización permite la entrega de los mensajes a destinos finales móviles o duplicados. Como resultado, una red DOLR provee una plataforma en la que implementar aplicaciones distribuidas.

Algoritmo

API (Interfaz de programación de aplicaciones)

Tapestry provee una interfaz de comunicación mediante datagramas, con mecanismos adicionales para manipular la localización de los objetos.

A cada nodo de la red superpuesta se le asigna un único nodoID (identificador) de forma aleatoria, uniformemente distribuido en un gran espacio de identificadores. A un mismo host físico le puede corresponder más de uno de estos nodos virtuales. A los puntos finales se les asigna de igual manera unos identificadores únicos llamados GUID (identificador único global, en inglés: globally unique identifier). Tapestry utiliza un espacio de identificadores con valores de 160 bits. Tapestry asume que los NodoIDs y GUIDs son distribuidos de manera más o menos uniforme, lo que puede lograrse mediante el uso de un algoritmo de hash seguro, como SHA-1, almacenado cada nodo de la red superpuesta varios de estos identificadores diferentes. De este modo decimos que un nodo tiene nodoID y un objeto tiene un GUID.

De los experimentos se demuestra la eficiencia de Tapestry aumenta con el tamaño de la red, por lo que, si hay varias aplicaciones que comparten la misma red superpuesta, aumenta la eficiencia. Para diferenciar entre las aplicaciones y permitir su coexistencia en la misma red, se utiliza un identificador de aplicación único, el cual irá incluido en los mensajes de cada aplicación. Este identificador se usara para reconocer a que proceso o aplicación pertenece cada mensaje, cumpliendo un papel similar al de los puertos en TCP/IP. Tapestry utiliza una política de best-effort (mejor esfuerzo) para publicar y encaminar objetos.

Teniendo en cuenta las definiciones anteriores, nos encontramos 4 tipos de mensajes, con los identificadores que contienen:

• PublishObject(GUID, ID de aplicación): para publicitar o hacer disponible un objeto en el nodo local, se realiza mediante best-effort y no recibe ninguna confirmación o acuse de recibo.
• UnPublishObject(GUID, ID de aplicación): pretende, mediante best-effort, eliminar la localización de un objeto en el mapeado.
• RouteToObject(GUID, ID de aplicación): para encaminar un mensaje a la localización de un objeto con GUID.
• RouteToNode(nodoID, ID de aplicación): para encaminar el mensaje a una aplicación determinada de un nodo determinado, requiere de especificación de destino exacta para poder entregar la carga útil.

Encaminamiento y localización de objetos

Tapestry asigna de manera dinámica cada identificador a un único nodo activo, llamado raíz del identificador o G_R. Si existe un nodo N con N_id = G, entonces este nodo será el raíz de G. Para entregar mensajes, cada nodo contiene una tabla de encaminamiento formada por los nodoIDs y las direcciones IP de los nodos vecinos. Cuando se encamina hacia el G_R, los mensajes se envían a través de los enlaces vecinos a los nodos cuyos nodoIDs son progresivamente más cercanos a G en el espacio de identificadores, esto se consigue incrementando el sufijo de encaminamiento.

Malla de encaminamiento

Tapestry utiliza tablas locales en cada nodo, llamadas tablas de vecindario, para encaminar mensajes al ID de destino dígito por dígito. Cada mapa de vecinos tiene múltiples niveles, donde cada nivel contiene enlaces a nodos que emparejan hasta una determinada posición dígitos en el ID. La i-ésima entrada primaria en el nivel j-ésimo es el ID y la ubicación del nodo más cercano, que comienza con el prefijo (N, j-1) + i. Esto significa que el nivel 1 tiene enlaces a nodos que no tienen nada en común, el nivel 2 tiene el primer dígito en común, etc. Debido a esto, el encaminamiento toma aproximadamente \ log_B N saltos en una red de tamaño N e IDs de base B. Si no puede encontrarse una ID exacta, la tabla de encaminamiento encaminará hasta el nodo obtenido más cercano. Por la tolerancia a fallos, los nodos mantienen c enlaces secundarios de tal manera que la tabla de encaminamiento tiene un tamaño c * B * \ log_B N.

Publicación y localización de objetos

Los participantes de la red pueden publicar objetos mediante el encaminamiento periódico de un mensaje a través del nodo raíz. Cada nodo a lo largo del camino almacena un puntero mapeando el objeto. Varios servidores pueden publicar punteros al mismo objeto. Los enlaces redundantes son priorizados por la latencia y / o localización.

Los objetos se encuentran mediante el encaminamiento de un mensaje hacia el nodo raíz del objeto. Cada nodo a lo largo del camino comprueba el mapeo y redirige la solicitud adecuadamente. El efecto de enrutamiento es la convergencia de caminos cercanos dirigiéndose al mismo destino.

Nodos dinámicos

Inserción de un nodo

Se requieren condiciones para insertar un nuevo nodo N en la red superpuesta. N podría convertirse en raíz de objetos existentes, las referencias a esos objetos deben moverse a N para mantener los objetos disponibles.Los algoritmos deben construir una tabla de encaminamiento óptima para N. Los nodos cercanos a N son informados y pueden considerar incluir a N en sus tablas de encaminamiento para hacerlas más óptimas.

El nuevo nodo se convierte en la raíz de su nodoID. La raíz busca la longitud del prefijo más largo de la ID que comparte. Entonces se envía un mensaje de multidifusión que llega a todos los nodos existentes que comparten el mismo prefijo. Estos nodos, a continuación, añaden el nuevo nodo a sus tablas de enrutamiento. El nuevo nodo puede hacerse cargo de ser la raíz de algunos de los objetos de la raíz. Los nodos se comunicarán con el nuevo nodo para proporcionarle una lista temporal de los nodos vecinos. Tras esto, el nuevo nodo, realiza una búsqueda del vecino más cercano iterativo para llenar todos los niveles en su tabla de enrutamiento.

Salida voluntaria de un nodo

Para salir de la red, un nodo transmite su intención de marcharse y transmite el nodo de sustitución para cada nivel en las tablas de enrutamiento de los otros nodos. Los objetos pertenecientes al nodo que está saliendo de la red se redistribuyen o reponen de copias redundantes.

Salida involuntaria de un nodo (fallo)

Para detectar fallos los nodos utilizan balizas periódicamente, para detectar posibles caídas de nodos y enlaces. El fallo inesperado de un nodo se maneja a través de la redundancia en la red y de los punteros de copia de seguridad para restablecer los vínculos dañados de la red. Esta forma de adaptarse a fallos es muy eficaz y hace que Tapestry tenga casi un 100% de éxito en el encaminamiento de mensajes a nodos y objetos.

Arquitectura e implementación

Arquitectura

En la cima de las capas de la arquitectura de un nodo tenemos las aplicaciones que se ejecutan sobre la red de Tapestry, justo sobre la capa de interfaz de aplicación (API). Bajo esta capa se encuentra una capa compuesta por el router, el cual procesa el encaminamiento y la localización de mensajes, y los componentes de gestión del nodo dinámico, que manejan la llegada y salida de los nodos de la red. Estos dos componentes se comunican a través d la tabla de encaminamiento y la base de datos de punteros a objetos. Por último tenemos las capas de administración de enlaces vecinos y de transporte, las cuales, juntas, proporcionan una capa de mensajería entre nodos.

Transporte

La capa de transporte provee la abstracción de los canales de comunicación entre nodos de la red superpuesta y corresponde a la capa 4 del modelo OSI.

Enlaces vecinos

Sobre la capa de transporte, se encuentra la capa de enlaces vecinos. Esta capa proporciona capacidades de operar con datagramas seguras pero poco fiables a las capas superiores, incluyendo la fragmentación y ensamblado de mensajes largos. La primera vez que una capa superior quiere comunicarse con otro nodo, debe proporcionar la dirección física de destino y, si desea una comunicación segura, también debe proporcionar una clave publica para el nodo remoto. La capa de enlaces vecinos utiliza esta información para establecer una conexión con el nodo remoto.

Para evitar un uso excesivo de los recursos, la capa de enlaces vecinos puede cerrar algunas conexiones periódicamente. Estas conexiones se volverán a abrir bajo demanda.

Una función importante de esta capa es la continua monitorización y adaptación de los enlaces. Esto proporciona detección de errores a través de mensajes Keep-alive.

Esta capa además optimiza el procesado de mensajes analizando las cabeceras y deserializando el contenido del mensaje solo cuando se requiere. Por último la autenticación nodo y de código de mensaje (MACs) se pueden integrar en esta capa para conseguir una mayor seguridad.

Router

Incluidas en esta capa están la tabla de encaminamiento y los punteros a objetos.

El router examina el GUID de destino de los mensajes y determina su siguiente salto usando la tabla de encaminamiento y los puntero al objeto. Entonces los mensajes se devuelven a la capa de enlaces vecinos para su entrega.

Tanto la tabla de encaminamiento como la base de datos de punteros están siendo modificadas continuamente por las capas de gestión del nodo dinámico y de enlaces vecinos.

Implementación

Implementación de un nodo Tapestry

Tapestry requiere una capa I/O asíncrona y un modelo eficiente para la comunicación y control de los componentes de la red.

Se implementan capas basadas en TCP y UDP. TCP proporciona control de flujo y congestión. Su desventaja son grandes configuraciones de conexión, un uso del ancho de banda poco óptimo y el consumo de descriptores de archivo (un recurso limitado). Por otro lado, UDP, por sí solo, no proporciona control de flujo ni congestión y puede consumir un gran ancho de banda, causando congestión si se usa en un gran área. Para corregir esto, la capa UDP contiene un control de congestión similar al de TCP y limitaciones en su capacidad de retransmisión. Sin embargo UDP cuenta con la ventaja de no tener el problema de consumo de los descriptores de archivo.

Virtualización del nodo

Podemos asignar varias instancias virtuales a una misma máquina física. Para reducir al mínimo la sobrecarga de memoria y computacional que esto supone en la máquina física podemos usar una máquina virtual java (JVM).

Todas las instancias virtuales que pertenecen a la misma máquina física comparten un solo hilo de ejecución de la JVM (solo una instancia virtual puede interactuar en un instante de tiempo). Cada instancia virtual contiene sus propios datos, que no comparte con el resto de instancia pertenecientes a la misma máquina física.

Un efecto de esta virtualización es el retardo introducido por la CPU entre los nodos. Durante los periodos de alta carga de la CPU, este retardo puede afectar significativamente en el rendimiento. Esto debe ser considerado al interpretar el funcionamiento de la red.

Aplicaciones

Tapestry proporciona una red de encaminamiento de superposición que es estable bajo una variedad de condiciones de la red. Esto proporciona una infraestructura ideal para aplicaciones y servicios distribuidos. Algunas aplicaciones basadas en Tapestry son:

• Oceanstore: Utilidad de almacenamiento distribuido en PlanetLab
• Mnemosyne: Sistema de archivos del Steganographic
• Bayeux: Organizador automático de aplicaciones de multidifusión
• SpamWatch: Filtro de spam descentralizado

Véase también

• CAN(Content Addressable Network)
• Chord
• Kademlia
• PASTRY (P2P)

Enlaces externos

• Chimera Project an implementation of Tapestry (ca. 2007)

• Datos: Q3515447